package java学习.算法.动态规划.暴力递归与动态规划;

import java.util.List;

/**
 * **************
 * 项目名称: 蓝桥杯 <br/>
 * 文件名称:  <br/>
 * 文件描述: 这里添加您的类文件描述，说明当前文件要包含的功能。 <br/>
 * 文件创建：刘世锦 <br/>
 * 创建时间: 2022/5/17 <br/>
 *
 * @version v1.0 <br/>
 * @update [序号][日期YYYY-MM-DD][更改人姓名][变更描述]<br/>
 * *************
 */
public class 背包价值问题 {
    /**
     * 给定两个长度都为N的数组weights和values，weight[i]和values[i]分别代表i号物品的重量和价值。
     *
     * 给定一个正数bag，表示一个载重bag的袋子，你装的物品不能超过这个重量。返回你能装下最多的价值是多少？
     */
    // index... 最大价值
    // 0..index-1上做了货物的选择，使得你已经达到的重量是多少 alreadyW
    // 如果返回-1，认为没有方案
    // 如果不返回-1，认为返回的值是真实价值
    public static int bagquestion(int[] w, int[] v , int index, int curw,int bag ){
        if (bag<0){
            return -1;
        }

        // 数组的最后一个是 w.length-1,此时已经数组越界
        if (index == w.length) {
            return 0;
        }
        int val= bagquestion(w,v,index+1,curw,bag); // 没要当前物品
        int valyes = 0;
        if (curw+w[index]<bag){
//            如果 此时加上下一个
             valyes= bagquestion(w,v,index+1,curw+w[index],bag) + v[index];
        }
        return Math.max(val,valyes);
    }
    public static int process(int[] w, int[] v, int index, int alreadyW, int bag) {
        // base case
        if (alreadyW > bag) {
            return -1;
        }
        // 重量没超
        if (index == w.length) {
            return 0;
        }
        // 当前不选择index的货物情况下，后续的价值
        // 无需传递当前index的重量，且p1就是总价值
        int p1 = process(w, v, index + 1, alreadyW, bag);
        // 当前选择了index的货物，把重量加上，继续向下递归
        int p2next = process(w, v, index + 1, alreadyW + w[index], bag);
        // p2表示要了当前货物之后总价值应该是后续价值加上当前价值
        int p2 = -1;
        if (p2next != -1) {
            p2 = v[index] + p2next;
        }
        return Math.max(p1, p2);

    }
    public static int maxValue(int[] w, int[] v, int bag) {
        return process(w, v, 0,0, bag);
    }
    public static int maxValue1(int[] w, int[] v, int bag) {
        return bagquestion(w, v, 0,0, bag);
    }
// 被换班人 申请换班班次 shiftReason 换班管理 换班申请
//    dp[i][j] 含义： 表示 从下标 0~i 的物品，放进j容量中 的最大价值 value
//    递推公式 dp[i][j] = max(dp[i-1][j],dp[i-1][j-weight[i]]+value[i])
//    例子： dp[1][4] = dp[0][4] (不加), dp[0][4-weight[i]] (加 )<已加前一个的物品，容量-现在要加的重量>+value[i] 要加的价值
    public static int dpWay(int[] w, int[] v, int bag) {
        int N = w.length;
        int[][] dp = new int[N + 1][bag + 1];
        for (int index = N - 1; index >= 0; index--) {
            for (int rest = 1; rest <= bag; rest++) {
                dp[index][rest] = dp[index + 1][rest];
                if (rest >= w[index]) {
                    dp[index][rest] = Math.max(dp[index][rest], v[index] + dp[index + 1][rest - w[index]]);
                }
            }
        }
        return dp[0][bag];
    }

    public static void main(String[] args) {
        int[] weights = { 3, 2, 4, 7 };
        int[] values = { 5, 6, 3, 19 };
        int bag = 11;
        System.out.println(maxValue(weights, values, bag));
        System.out.println(maxValue1(weights, values, bag));

        System.out.println(dpWay(weights, values, bag));
    }
}
